The present invention is related to error detection in data transmission systems, and particularly to the fast parallel calculation of cyclic redundancy checks (CRCs).
The purpose of error detection systems is to detect whether data messages are corrupted during transmission. If the presence of one or more errors is detected in a received data message, the data message can either be ignored, for example in voice and video applications, a retransmission can be requested, for example in Ethernet, Sonet, Hyperlan, and other types of data communication systems, or the error can be corrected, as in forward error correction systems. Being able to detect errors, whether or not the errors are corrected, means that the introduction of errors does not have the same implication as if the errors go undetected, that is, it is not as important to avoid the occurrence of errors if they can be detected. This allows data network systems to be designed such that errors are allowed to occur, typically so long as they occur at or below a known manageable rate. The result is that data can be transmitted at a lower power level and at higher transmission rates. Because of this, data can be transmitted farther and channel capacity can be increased.
Modern data networks transmit data at ever higher data rates, thus received data needs to be processed quickly. Accordingly, the trend in cyclical redundancy checking is to process more bits of data simultaneously. This means that new data network protocols use longer polynomials in the processing of the CRCs, as described below.
But these longer polynomial expressions require increasingly complex circuitry to generate and verify these CRCs. Increasingly complex circuitry consumes more power and has longer delay paths and higher fan-outs that result in slower operation. For example, a 32 bit polynomial may require 32 circuits having on the order of 32 inputs each, for over 900 total logic gate inputs.
Thus what is needed are circuits, methods, and apparatus for rapidly handling these longer polynomials without greatly increasing the complexity of the circuitry required to process them.